<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Quick Sort</title>
</head>
<body>
</body>


<script>

    function exch(arr, a, b) {
      let t = arr[a];
      arr[a] = arr[b];
      arr[b] = t;
    }

    function partition(arr, lo, hi) {
      let i = lo;
      let j = hi + 1;
      let v = arr[lo];
      while (true) {
        // 把选定的v 比v小的都放左边，比v大的都放右边
        while (arr[++ i] < v) {
          if (i == hi)
            break;
        }
        while (arr[-- j] > v) {
          if (j == lo)
            break;
        }
        //如果左右两边指针相遇，找j的位置结束
        if (i >= j)
          break;
        exch(arr, i, j);
      }
      //把v放到正确位置，返回j（v）的位置
      exch(arr, lo, j);
      return j;
    }

    function sort(arr, lo, hi) {
      if (lo >= hi) return;
      let j = partition(arr, lo, hi);
      sort(arr, lo, j - 1);
      sort(arr, j + 1, hi);
    }

    let test_arr = [5.5, 3, 10 ,7, 4, 6, 8, 9, 2];
    sort(test_arr, 0, test_arr.length - 1);

    console.log(test_arr);











//    function partition2(arr, lo, hi) {
//      let i = lo;
//      let j = hi + 1;
//      let v = arr[lo];
//      while (true) {
//        while (arr[-- j] > v) {
//          if (j == lo)
//            break;
//        }
//        while (arr[++ i] < v) {
//          if (i == hi)
//            break;
//        }
//        if (i >= j)
//          break;
//        exch(arr, lo, hi);
//      }
//      exch(arr, lo, j);
//      return j;
//    }

































</script>

</html>